#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int nthUglyNumber(int n) {
        //  vector<long long> ans;
        unordered_set<long long> s;
        priority_queue<long long, vector<long long>, greater<long long>> q;
        s.insert(1);
        q.push(1);
        long long it = 0;
        for (int i = 1; i <= n; i++) {
            it = q.top();
            q.pop();
            if (!s.count(it * 2)) {
                s.insert(it * 2);
                q.push(it * 2);
            }
            if (!s.count(it * 3)) {
                s.insert(it * 3);
                q.push(it * 3);
            }
            if (!s.count(it * 5)) {
                q.push(it * 5);
                s.insert(it * 5);
            }
        }
        return it;
    }
};